/*!
 * \file bbmaxclique.c
 *
 * \date Sep 24, 2013
 * \author Ricardo C. Corrêa (correa@lia.ufc.br)
 *
 * \brief Branch and bound algorithm for maximum clique.
 */

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <sys/time.h>

#include <bitmap.h>
#include <graph.h>
#include <grinput.h>
#include <heurColoring.h>
#include <mcr.h>

typedef struct {
	Node node;
	BitMap * B;
	int * R; //!< sorted array of vertices
	int * C; //!< sorted colors
	int i;
	int lim;
} Subproblem;

static int (*coloring)(BitMap *, int, int *, int *);

static int (*sortVertices)(Graph *, int *);

void bb_maxClique(Graph * g, int maxdeg, long long * nsubps, long long * memsz) {
	int n = g->n;

	Subproblem stack[++maxdeg];
	Subproblem * subp = stack;
	*memsz = maxdeg * sizeof(Subproblem);

	BitMap * vec = newBitMapVector(maxdeg, n);
	stack->R = (int *) calloc((maxdeg << 1) * n, sizeof(int));
//	*memsz += maxdeg * nnodes * WSIZE + (maxdeg << 1) * n * sizeof(int);

	int i, p;
	for (i = 0, p = 0; i < maxdeg; subp++, i++, p += n) {
		subp->B = vec + i;
		subp->R = stack->R + p;
		p += n;
		subp->C = stack->R + p;
	}
	subp = stack;
	addAllElements(subp->B);

	initHeur(g);

	//initialize with a maximal clique
	if (g->maxcq < 0)
		g->maxcq = maxClique(subp->B);

	//build an initial coloring
	subp->lim = g->maxcq;
	subp->i = mcsColoring_f(subp->B, subp->lim,	subp->R, subp->C);

	(*nsubps) = 1;

	int v = 0;
	int topC = 0;
	while (topC >= 0) {
		//get the next vertex in the candidate set
		subp->i--;

		if (subp->i < 0 || topC + subp->C[subp->i] + subp->lim <= g->maxcq) {
			if (topC > g->maxcq)
				g->maxcq = topC;
			subp--;
			topC--;
		} else {
			v = subp->R[subp->i];
			setElement(&subp->node, v);
			delElement(subp->B, &subp->node);

			//Calculate the new candidate vector
			Subproblem * newsubp = subp + 1;
			intersectOf(newsubp->B, neig(g, v), subp->B);

			//Build a coloring for the candidate's vector
			newsubp->lim = g->maxcq - ++topC;
			newsubp->i = coloring(newsubp->B, newsubp->lim, newsubp->R,	newsubp->C);
			(*nsubps)++;
			subp = newsubp;
		}
	}

	*memsz += getMemSize();
	freeBitMap(stack->B);
	free(stack->R);

	closeHeur();
}

int main(int argc, char *argv[]) {
	char name[200];
	FILE* graphFile = NULL;
	FILE* outFile = NULL;

	outFile = fopen(argv[1], "a+");
	graphFile = fopen(argv[2], "r");
	strcpy(name, argv[2]);
	int algo;
	if (argc >= 4)
		algo = atoi(argv[3]);
	else
		algo = 1;

	switch (algo) {
	case 1: {
		coloring = greedyColoring;
		break;
	}
	case 2: {
		coloring = mcsColoring;
		break;
	}
	case 3: {
		printf("Not implemented.\n");
		exit(0);
		break;
	}
	}

	int order;
	if (argc >= 5)
		order = atoi(argv[4]);
	else
		order = 1;

	switch (order) {
	case 1: {
		sortVertices = heapMcr;
		break;
	}
	case 2: {
		sortVertices = listMcr;
		break;
	}
	case 3: {
		sortVertices = decExdegree;
		break;
	}
	case 4: {
		sortVertices = decDegree;
		break;
	}
	}

	Graph * g = readDimacsGraph(graphFile);

	struct timeval tvoi, tvoe;
	float renumberTime;

	int maxdeg;
	gettimeofday(&tvoi, NULL);
	int R[g->n];
	maxdeg = sortVertices(g, R);

	Graph * gg = newRenumbered(g, R);
	gettimeofday(&tvoe, NULL);

	printf("maxdeg=%d\n",maxdeg);
	fflush(NULL);

	renumberTime = (tvoe.tv_sec - tvoi.tv_sec) + (tvoe.tv_usec - tvoi.tv_usec) / 1000000000.0;
	delGraph(g);
	free(g);

	gg->maxcq = -1;
	if (argc >= 6)
	{
		char * fnm = strstr(argv[2], "random/");
		if (fnm != NULL)
		{
			fnm = strchr(fnm, '/')+1;
		}
		else
		{
			fnm = strrchr(argv[2], '/');
			if (fnm == NULL)
				fnm = argv[2];
			else
				fnm = fnm + 1;
		}
		fnm = strtok(fnm, ".");

		FILE * maxFile = fopen(argv[5], "r");
		char linestr[100];
		char * solfilename;
		while (!feof(maxFile) && gg->maxcq < 0)
		{
			if (fgets(linestr, 100, maxFile) == NULL)
				break;
			solfilename = strtok(linestr, " ");
			int maxcq = atoi(strtok(NULL, " "));
			printf("%s %s\n", fnm, solfilename);
			fflush(NULL);
			if (!strcmp(fnm, solfilename))
			{
				gg->maxcq = maxcq;
				printf("%s %d\n", solfilename, gg->maxcq);
				fflush(NULL);
			}
		}
		fclose(maxFile);
	}

	long long memsz;
	long long ndolls;

	struct timespec start, end;
	struct timeval tvs, tve;
	float optimizationTime;

	gettimeofday(&tvs, NULL);
	bb_maxClique(gg, maxdeg, &ndolls, &memsz);
	gettimeofday(&tve, NULL);
	start.tv_sec = tvs.tv_sec;
	start.tv_nsec = tvs.tv_usec * 1000;
	end.tv_sec = tve.tv_sec;
	end.tv_nsec = tve.tv_usec * 1000;
	optimizationTime = (end.tv_sec - start.tv_sec);
	optimizationTime += (end.tv_nsec - start.tv_nsec) / 1000000000.0;

	printf(
			"%s \t n=%d  colorHeur=%d  sortVert=%d  sol=%d  initTime=%f  ndolls=%lld  time=%f  mem=%fKB  graphmem=%fKB \n",
			name, gg->n, algo, order, gg->maxcq, renumberTime, ndolls,
			optimizationTime, memsz / 1024.0, gg->matrixsize / 1024.0);
	fprintf(outFile,
			"%s \t %d \t %d \t %d \t %d \t %f \t %lld \t %f \t %f \t %f\n",
			name, gg->n, algo, order, gg->maxcq, renumberTime, ndolls,
			optimizationTime, memsz / 1024.0, gg->matrixsize / 1024.0);

	delGraph(gg);
	free(gg);
	fclose(outFile);
	fclose(graphFile);
	return 0;
}
